def counting_sort(arr):
    n = len(arr)
    output = [0] * n
    count = [0] * 100

    # Store count of each element
    for i in range(n):
        count[arr[i]] += 1

    print("Count array:", count)

    # Change count[i] so that count[i] now contains actual position of this character in output array
    for i in range(1, 100):
        count[i] += count[i - 1]

    print("Count array after updating:", count)

    # Build the output array
    for i in range(n - 1, -1, -1):
        print("i:", i, "arr[i]:", arr[i], "count[arr[i]]:", count[arr[i]])
        output[count[arr[i]] - 1] = arr[i]
        count[arr[i]] -= 1
        print("Output array:", output, "Count array:", count)

    return output

if __name__ == '__main__':
    arr = [3, 2, 1, 5, 4, 7, 99, 6, 9, 8, 8, 2, 1]
    print("Original array:", arr)
    sorted_arr = counting_sort(arr)
    print("Sorted array:", sorted_arr)